package leetcode;

import javax.crypto.spec.OAEPParameterSpec;
import java.util.LinkedList;

//993. 二叉树的堂兄弟节点
public class LC993 {

    int x;
    int xParent = -1;
    int xDeepth = -1;
    boolean xIsFound = false;
    int y ;
    int yParent = -1;
    int yDeepth = -1;
    boolean yIsFound = false;

    // dfs遍历二叉树
//    public void dfs(TreeNode node, int parent, int deepth) {
//        if (node == null) return;
//        if (node.val == x) {
//            xParent = parent;
//            xDeepth = deepth;
//            xIsFound = true;
//        } else if (node.val == y) {
//            yParent = parent;
//            yDeepth = deepth;
//            yIsFound = true;
//        }
//        if (xIsFound && yIsFound) return;
//        dfs(node.left,node.val,deepth + 1);
//        dfs(node.right,node.val,deepth + 1);
//    }
//
//    public boolean isCousins(TreeNode root, int x, int y) {
//        this.x = x;
//        this.y = y;
//        dfs(root,0,0);
//        if (xIsFound && yIsFound && xDeepth == yDeepth && xParent != yParent)
//            return true;
//        return false;
//    }

        //BFS遍历
        public boolean isCousins(TreeNode root, int x, int y) {
            LinkedList<TreeNode> queue = new LinkedList<>();
            LinkedList<int[]> deepthq = new LinkedList<>();
            boolean xIsFound = false;
            boolean yIsFound = false;
            int xDeepth = -1;
            int yDeepth = -1;
            int xParent = -1;
            int yParent = -1;

            queue.addFirst(root);
            deepthq.addFirst(new int[]{0,0}); // int[0] 保存父亲节点，int[1]保存深度
            while (!queue.isEmpty()) {
                TreeNode node = queue.removeFirst();
                int[] nodeInfo = deepthq.removeFirst();
                if (node.val == x) {
                    xIsFound = true;
                    xParent = nodeInfo[0];
                    xDeepth = nodeInfo[1];
                } else if (node.val == y) {
                    yIsFound = true;
                    yParent = nodeInfo[0];
                    yDeepth = nodeInfo[1];
                }
                if (xIsFound && yIsFound && xParent != yParent && xDeepth == yDeepth)
                    return true;
                if (node.left != null) {
                    queue.addLast(node.left);
                    deepthq.addLast(new int[]{node.val,nodeInfo[1] + 1});
                }
                if (node.right != null) {
                    queue.addLast(node.right);
                    deepthq.addLast(new int[]{node.val,nodeInfo[1] + 1});
                }
            }
            return false;
        }

}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}